package com.datastructures2.字符串.字符串排序;

import edu.princeton.cs.algs4.StdRandom;

/**
 * 三向字符串快速排序
 * @author MaoLin Wang
 * @date 2020/2/2520:07
 */
public class Quick3string {
    private static final int CUTOFF =  15;

    private Quick3string() { }



    public static void sort(String[] a) {
        //以统一随机的顺序重新排列指定数组的元素。
        StdRandom.shuffle(a);
        sort(a, 0, a.length-1, 0);
    }

    private static int charAt(String s, int d) {
        if (d == s.length()) return -1;
        return s.charAt(d);
    }


    private static void sort(String[] a, int lo, int hi, int d) {

        if (hi <= lo + CUTOFF) {
            insertion(a, lo, hi, d);
            return;
        }

        int lt = lo, gt = hi;
        int v = charAt(a[lo], d);
        int i = lo + 1;
        while (i <= gt) {
            int t = charAt(a[i], d);
            if      (t < v) exch(a, lt++, i++);
            else if (t > v) exch(a, i, gt--);
            else              i++;
        }

        // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
        sort(a, lo, lt-1, d);
        if (v >= 0) sort(a, lt, gt, d+1);
        sort(a, gt+1, hi, d);
    }

    // sort from a[lo] to a[hi], starting at the dth character
    private static void insertion(String[] a, int lo, int hi, int d) {
        for (int i = lo; i <= hi; i++)
            for (int j = i; j > lo && less(a[j], a[j-1], d); j--)
                exch(a, j, j-1);
    }

    // exchange a[i] and a[j]
    private static void exch(String[] a, int i, int j) {
        String temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    private static boolean less(String v, String w, int d) {
        assert v.substring(0, d).equals(w.substring(0, d));
        for (int i = d; i < Math.min(v.length(), w.length()); i++) {
            if (v.charAt(i) < w.charAt(i)) return true;
            if (v.charAt(i) > w.charAt(i)) return false;
        }
        return v.length() < w.length();
    }

    public static void main(String[] args) {
        String[]a=new String[18];
        a[0]="she";
        a[1]="sells";
        a[2]="seashells";
        a[3]="by";
        a[4]="the";
        a[5]="sea";
        a[6]="shore";
        a[7]="the";
        a[8]="shells";
        a[9]="she";
        a[10]="sells";
        a[11]="are";
        a[12]="surely";
        a[13]="seashells";
        a[14]="areaa";
        a[15]="thema";
        a[16]="byebye";
        a[17]="seathells";
        sort(a);
        for (String s:a){
            System.out.println(s);
        }
    }


}
